ALGORITHMS FOR THE ASSIGNMENT PROBLEM
Introduction
With this package, I provide some MATLAB-functions regarding the
rectangular assignment problem. This problem appears for example in
tracking applications, where one has M existing tracks and N new
measurements. For each possible assignment, a cost or distance is computed.
All cost values form a matrix, where the row index corresponds to the
tracks and the column index corresponds to the measurements. The provided
functions return an optimal or suboptimal assignment - in the sense of
minimum overall costs - for the given matrix.
In the process of gating, typically very unlikely assignments are
forbidden. The given functions can handle forbidden assignments, which are
marked by setting the corresponding assignment cost to infinity.
The optimal solution is computed using Munkres algorithm, also known as
Hungarian Algorithm.
Functions contained in this package
assignmentallpossible.m
Computes the optimal assignment by recursively stepping over all possible
assignment vectors. Used for reference computation.
assignmentoptimal.m and assignmentoptimal.c
Computes the optimal assignment (minimum overall costs) using Munkres algorithm.
assignmentsuboptimal1.m and assignmentsuboptimal2.c
Computes a suboptimal solution. Good for cases with many forbidden assignments.
assignmentsuboptimal1.m and assignmentsuboptimal2.c
Computes a suboptimal solution. Good for cases without forbidden assignments.
testassign.m
Compares the algorithms regarding performance and optimality of solutions.
Usage
The first four functions are called like the following:
[assignment, cost] = assignment_xx(distMatrix);
(Replace "_xx" by "optimal", for example). Type "help assignment_xx" for more hints to the
different algorithms.
Take care that all costs/distances are positive or zero!
How to use mex-files
The C language source files are so-called mex-files for MATLAB. You should be able to compile
these functions manually on all systems by typing
mex assignmentoptimal.c
mex assignmentsuboptimal1.c
mex assignmentsuboptimal2.c
in MATLAB. If you have never used the mex-command before, you first have to
select a compiler. I suggest to use one of the built-in compilers that
come with Matlab.
The mex-command creates a file with a system-dependent extension, in Windows it is .mexw32. As
soon as this file in generated, you can use it as you would call a MATLAB function. When both
mex- and m-file of the same name are on the MATLAB path, the mex-file is chosen.
The mex-files can save computation time up to a factor of 10 or 20. Use the test functions
testassignment.m with your own preferences and have a look at the profiler output.
By the way, you will find that in some cases the mex-implementations of the suboptimal
algorithms need a longer computation time than the optimal algorithm. The functions are much
faster than the MATLAB-implementations, but they can still be improved (If you do, please let
me know).
Using the functions from C
The mex-files always contain a function called "mexFunction" that is needed for MATLAB and
a function called "assignment_xx". You can use the second if you want to apply the algorithms
directly from C. If you do not have MATLAB installed, you have to replace the mx-functions
(e.g. mxCalloc) by ordinary C-functions and delete the two include lines.
If you decide to use the functions in C, you might need the column indices to start from 0,
not from 1 as in MATLAB. Just delete the definition of ONE_INDEXING and you are done. If you
do not need to handle infinite values in your applications, also delete the definition of
CHECK_FOR_INF.
Two more points to take care of when using C: The assignment vector is defined as a double
precision array, as MATLAB uses double precision values anyway. When referencing elements
with the computed assignment vector in C, you have to change all function declarations to use
integer values. Further, the distance or cost matrix of size MxN is defined as a double
precision array of N*M elements. Matrices are saved MATLAB-internally in row-order (i.e. the
matrix [1 2; 3 4] will be stored as a vector [1 3 2 4], NOT [1 2 3 4]).
Problems
I have not tested the functions on any other system than Windows with MATLAB 6.5.1. But as I do
not use any sophisticated functions or special toolboxes, I expect the functions to run on all
systems without problems. If you have problems anyway, feel free to contact me.
If you find any bugs or errors, please give me the chance to correct them and drop me an
E-mail.
Contact
Dipl.-Ing. Markus Buehren
Stuttgart, Germany
mb_matlab@gmx.de
http://www.markusbuehren.de
Version
Last modified 30.01.2008
Latest version on Matlab Central.